home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxsuper.h < prev    next >
C/C++ Source or Header  |  1998-01-28  |  16KB  |  447 lines
  1. /* classes: h_files */
  2.  
  3. #ifndef RXSUPERH
  4. #define RXSUPERH
  5.  
  6. /*    Copyright (C) 1995, 1996 Tom Lord
  7.  * 
  8.  * This program is free software; you can redistribute it and/or modify
  9.  * it under the terms of the GNU Library General Public License as published by
  10.  * the Free Software Foundation; either version 2, or (at your option)
  11.  * any later version.
  12.  * 
  13.  * This program is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16.  * GNU Library General Public License for more details.
  17.  * 
  18.  * You should have received a copy of the GNU Library General Public License
  19.  * along with this software; see the file COPYING.  If not, write to
  20.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  21.  * Boston, MA 02111-1307, USA. 
  22.  */
  23.  
  24. /*  lord    Sun May  7 12:40:17 1995    */
  25.  
  26.  
  27.  
  28. #include "rxnfa.h"
  29.  
  30.  
  31.  
  32. /* This begins the description of the superstate NFA.
  33.  *
  34.  * The superstate NFA corresponds to the NFA in these ways:
  35.  *
  36.  * Superstate states correspond to sets of NFA states (nfa_states(SUPER)),
  37.  *
  38.  * Superstate edges correspond to NFA paths.
  39.  *
  40.  * The superstate has no epsilon transitions;
  41.  * every edge has a character label, and a (possibly empty) side
  42.  * effect label.   The side effect label corresponds to a list of
  43.  * side effects that occur in the NFA.  These parts are referred
  44.  * to as:   superedge_character(EDGE) and superedge_sides(EDGE).
  45.  *
  46.  * For a superstate edge EDGE starting in some superstate SUPER,
  47.  * the following is true (in pseudo-notation :-):
  48.  *
  49.  *       exists DEST in nfa_states s.t. 
  50.  *         exists nfaEDGE in nfa_edges s.t.
  51.  *                 origin (nfaEDGE) == DEST
  52.  *              && origin (nfaEDGE) is a member of nfa_states(SUPER)
  53.  *              && exists PF in possible_futures(dest(nfaEDGE)) s.t.
  54.  *                     sides_of_possible_future (PF) == superedge_sides (EDGE)
  55.  *
  56.  * also:
  57.  *
  58.  *      let SUPER2 := superedge_destination(EDGE)
  59.  *          nfa_states(SUPER2)
  60.  *           == union of all nfa state sets S s.t.
  61.  *                          exists PF in possible_futures(dest(nfaEDGE)) s.t.
  62.  *                            sides_of_possible_future (PF) == superedge_sides (EDGE)
  63.  *                          && S == dests_of_possible_future (PF) }
  64.  *
  65.  * Or in english, every superstate is a set of nfa states.  A given
  66.  * character and a superstate implies many transitions in the NFA --
  67.  * those that begin with an edge labeled with that character from a
  68.  * state in the set corresponding to the superstate.
  69.  * 
  70.  * The destinations of those transitions each have a set of possible
  71.  * futures.  A possible future is a list of side effects and a set of
  72.  * destination NFA states.  Two sets of possible futures can be
  73.  * `merged' by combining all pairs of possible futures that have the
  74.  * same side effects.  A pair is combined by creating a new future
  75.  * with the same side effect but the union of the two destination sets.
  76.  * In this way, all the possible futures suggested by a superstate
  77.  * and a character can be merged into a set of possible futures where
  78.  * no two elements of the set have the same set of side effects.
  79.  *
  80.  * The destination of a possible future, being a set of NFA states, 
  81.  * corresponds to a supernfa state.  So, the merged set of possible
  82.  * futures we just created can serve as a set of edges in the
  83.  * supernfa.
  84.  *
  85.  * The representation of the superstate nfa and the nfa is critical.
  86.  * The nfa has to be compact, but has to facilitate the rapid
  87.  * computation of missing superstates.  The superstate nfa has to 
  88.  * be fast to interpret, lazilly constructed, and bounded in space.
  89.  *
  90.  * To facilitate interpretation, the superstate data structures are 
  91.  * peppered with `instruction frames'.  There is an instruction set
  92.  * defined below which matchers using the supernfa must be able to
  93.  * interpret.
  94.  *
  95.  * We'd like to make it possible but not mandatory to use code
  96.  * addresses to represent instructions (c.f. gcc's computed goto).
  97.  * Therefore, we define an enumerated type of opcodes, and when
  98.  * writing one of these instructions into a data structure, use
  99.  * the opcode as an index into a table of instruction values.
  100.  * 
  101.  * Below are the opcodes that occur in the superstate nfa.
  102.  *
  103.  * The descriptions of the opcodes refer to data structures that are
  104.  * described further below. 
  105.  */
  106.  
  107. enum rx_opcode
  108. {
  109.   /* 
  110.    * BACKTRACK_POINT is invoked when a character transition in 
  111.    * a superstate leads to more than one edge.  In that case,
  112.    * the edges have to be explored independently using a backtracking
  113.    * strategy.
  114.    *
  115.    * A BACKTRACK_POINT instruction is stored in a superstate's 
  116.    * transition table for some character when it is known that that
  117.    * character crosses more than one edge.  On encountering this
  118.    * instruction, the matcher saves enough state to backtrack to this
  119.    * point later in the match.
  120.    */
  121.   rx_backtrack_point = 0,    /* data is (struct transition_class *) */
  122.  
  123.   /* 
  124.    * RX_DO_SIDE_EFFECTS evaluates the side effects of an epsilon path.
  125.    * There is one occurence of this instruction per rx_distinct_future.
  126.    * This instruction is skipped if a rx_distinct_future has no side effects.
  127.    */
  128.   rx_do_side_effects = rx_backtrack_point + 1,
  129.  
  130.   /* data is (struct rx_distinct_future *) */
  131.  
  132.   /* 
  133.    * RX_CACHE_MISS instructions are stored in rx_distinct_futures whose
  134.    * destination superstate has been reclaimed (or was never built).
  135.    * It recomputes the destination superstate.
  136.    * RX_CACHE_MISS is also stored in a superstate transition table before
  137.    * any of its edges have been built.
  138.    */
  139.   rx_cache_miss = rx_do_side_effects + 1,
  140.   /* data is (struct rx_distinct_future *) */
  141.  
  142.   /* 
  143.    * RX_NEXT_CHAR is called to consume the next character and take the
  144.    * corresponding transition.  This is the only instruction that uses 
  145.    * the DATA field of the instruction frame instead of DATA_2.
  146.    * The comments about rx_inx explain this further.
  147.    */
  148.   rx_next_char = rx_cache_miss + 1, /* data is (struct superstate *) */
  149.  
  150.   /* RX_BACKTRACK indicates that a transition fails.  Don't
  151.    * confuse this with rx_backtrack_point.
  152.    */
  153.   rx_backtrack = rx_next_char + 1, /* no data */
  154.  
  155.   /* 
  156.    * RX_ERROR_INX is stored only in places that should never be executed.
  157.    */
  158.   rx_error_inx = rx_backtrack + 1, /* Not supposed to occur. */
  159.  
  160.   rx_num_instructions = rx_error_inx + 1
  161. };
  162.  
  163. /* The heart of the matcher is a `word-code-interpreter' 
  164.  * (like a byte-code interpreter, except that instructions
  165.  * are a full word wide).
  166.  *
  167.  * Instructions are not stored in a vector of code, instead,
  168.  * they are scattered throughout the data structures built
  169.  * by the regexp compiler and the matcher.  One word-code instruction,
  170.  * together with the arguments to that instruction, constitute
  171.  * an instruction frame (struct rx_inx).
  172.  *
  173.  * This structure type is padded by hand to a power of 2 because
  174.  * in one of the dominant cases, we dispatch by indexing a table
  175.  * of instruction frames.  If that indexing can be accomplished
  176.  * by just a shift of the index, we're happy.
  177.  *
  178.  * Instructions take at most one argument, but there are two
  179.  * slots in an instruction frame that might hold that argument.
  180.  * These are called data and data_2.  The data slot is only
  181.  * used for one instruction (RX_NEXT_CHAR).  For all other 
  182.  * instructions, data should be set to 0.
  183.  *
  184.  * RX_NEXT_CHAR is the most important instruction by far.
  185.  * By reserving the data field for its exclusive use, 
  186.  * instruction dispatch is sped up in that case.  There is
  187.  * no need to fetch both the instruction and the data,
  188.  * only the data is needed.  In other words, a `cycle' begins
  189.  * by fetching the field data.  If that is non-0, then it must
  190.  * be the destination state of a next_char transition, so
  191.  * make that value the current state, advance the match position
  192.  * by one character, and start a new cycle.  On the other hand,
  193.  * if data is 0, fetch the instruction and do a more complicated
  194.  * dispatch on that.
  195.  */
  196.  
  197. struct rx_inx 
  198. {
  199.   void * data;
  200.   void * data_2;
  201.   void * inx;
  202.   void * fnord;
  203. };
  204.  
  205. #ifndef RX_TAIL_ARRAY
  206. #define RX_TAIL_ARRAY  1
  207. #endif
  208.  
  209. /* A superstate corr